\documentclass{article}
\usepackage[utf8]{inputenc} % un package
\usepackage[T1]{fontenc}      % un second package
\usepackage[francais]{babel}  % un troisième package
\usepackage{amsmath}
\usepackage{graphicx}

\title{Sécurité et Protocole}
\author{Alexandre Masson}
\date{11 Septembre 2013}

\begin{document}
\maketitle
\newpage
\section{11 Septembre 2013}
\paragraph{Éval}
cc + ct : note final cc+2*ct/3

\paragraph{} on évolue de l'antiquité à maintenant, on va faire le tour de la crypto
\begin{itemize}
\item algo chiffrement
\item chif symétrique
\item chiffrement asymétrique RSA
\item Protocole et sécurité
\item Modélisation et outil de vérification de la sécurité des protocoles
\item Échange quantique de clés

\end{itemize}
\subsection{Histoire}
\paragraph{stéganographie -> crypto} stéganographie : écriture couverte\\ 
faitts historiques : on constate que depuis la nuit des temps , on a la necessité de cacher des informations, toutefois, la plupart des méthodes anciennes fail si le message est intercepté.\\\\
\begin{itemize}

\item crypto : ecriture caché, les spartiates utilise des scytales (cf wiki) \\
Chiffre de césar : décalage alphabétique\\
\item[1580] chiffre par substitution de symboles -- Marie Stuart , mixe entre chiffrement (remplacé lettre par autre) et symboles (remplacer mot/autre)
\item[1586] traité des chiffres - chiffres de Vigenère
\item[1930] Enigma, machine qu'utilisait les allemands durant WWII.
\item[fin 20eme] Apparition du chiffrement clé publique
\end{itemize}

\paragraph{crypto en résumé}
c'est l'étude des algo et protocoles, preserver la confidentialité et garantir intégrité
\begin{itemize}
\item Echanges sécur
\item Confidentialité des transactions bancaires
\item protec des secrets
\end{itemize}

En résumé : profiter des faiblesses des chiffrements pour les dechiffrer.

\subsection{Codes et chiffres}
Code: table à double entrées en texte clair
\begin{tabular}{|c|c|}
\hline 
le sous marin est attend à & jean  \\ 
\hline 
10h & est là \\ 
\hline 
20h & n'est pas là \\ 
\hline 
\end{tabular}
problème : clé > message
\paragraph{les fonctions} fonction E encryption C=E(M,K) , decryptage, les algo sont publiques
\paragraph{chiffrement /decalage} on créer une table de substitution, pour remplacer notre alphabet par un autre, mais facilement decryptable, car pas tres complexe


decodagede  : uxegrrufpqeqjqdoqdgzbqfufbqg\\
ilsuffitdesexercerunpeu

\paragraph{chiffre par substitution} généralisation du chiffrement /decalage
la clé est une permutation P arbitraire des 26 lettres, toutefois il faut la partager\begin{itemize}
\item 2tablir une clef (ex: securite)
\item supprimer dans la clé les lettres qui apparaissent deux fois (ex: securite -> securit)
\item faire corespondrela premire lettre de la clé et celle de l'aplhabet, et continuer en enlevant les lettres présentent dnas la clé

\end{itemize}
 \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline 
a & b & c & d & e & f & g & h & i & j & k & l & m & n & o & p & q & r & s & t & u & v & w & x & y & z \\ 
\hline 
s & e & c & u & r & i & t & v & w & x & y & z & a & b & d & f & g & h & j & k & l & m & n & o & p & q \\ 
\hline 
\end{tabular} 
\paragraph{carré de vigenere}
on prend le texteqquel'on veux chiffrer NOUSSOMMESDECOUVERTS et la clé DECEPTION\\\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline 
c & e & n & e & s & t & p & a & s & t & r & o & p & c & o & m & p & l & i & q & u & e \\ 
\hline 
2 & 4 & 13 & 4 & 18 & 19 & 15 & 0 & 18 & 19 & 17 & 14 & 15 & 2 & 14 & 12 & 15 & 11 & 8 & 16 & 20 & 4 \\ 
\hline 
m & a & s & t & e & r & d & e & u & x & m & a & s & t & e & r & d & e & u & x & m & a \\ 
\hline 
12 & 0 & 18 & 19 & 4 & 17 & 3 & 4 & 20 & 23 & 12 & 0 & 18 & 19 & 4 & 17 & 3 & 4 & 20 & 23 & 12 & 0 \\ 
\hline 
14 & 4 & 31 & 23 & 22 & 36 & 18 & 4 & 38 & 42 & 29 & 14 & 33 & 21 & 18 & 29 & 18 & 15 & 28 & 39 & 32 & 4 \\ 
\hline 
14 & 4 & 5 & 23 & 22 & 10 & 18 & 4 & 12 & 16 & 3 & 14 & 5 & 21 & 18 & 3 & 18 & 15 & 2 & 13 & 6 & 4 \\ 
\hline 
o & e & f & x & w & k & s & e & m & q & d & o & f & v & s & d & s & p & c & n & g & e \\ 
\hline 
\end{tabular} \\

\paragraph{Chiffrement de Hill (ça tombe tout le temps au partiel)}
on prend une matrice 2x2 ou 3x3, et on prend les lettres du message par 2 (ou 3), et on fait un produit de matrice modulo 26 pour trouver quelle lettre chiffre les trois lettres du message.


Matrice de base\\
\begin{tabular}{|c|c|c|c|c|c|}
\hline 
1 & 1 & 10 & 25 & 0 & 9 \\ 
\hline 
21 & 18 & 21 & 0 & 1 & 0 \\ 
\hline 
0 & 0 & 1 & 24 & 0 & 17 \\ 
\hline 
\end{tabular} 
\newpage
L2 <- l2-21*l1
\begin{tabular}{|c|c|c|c|c|c|}
\hline 
1 & 1 & 10 & 25 & 0 & 9 \\ 
\hline 
0 & 23 & 19 & 5 & 1 & 19 \\ 
\hline 
0 & 0 & 1 & 24 & 0 & 17 \\ 
\hline 
\end{tabular} \\
L2 = 17*L2
\begin{tabular}{|c|c|c|c|c|c|}
\hline 
1 & 1 & 10 & 25 & 0 & 9 \\ 
\hline 
0 & 1 & 11 & 7 & 17 & 11 \\ 
\hline 
0 & 0 & 1 & 24 & 0 & 17 \\ 
\hline 
\end{tabular}  \\
L1 <- L1 - L2
\begin{tabular}{|c|c|c|c|c|c|}
\hline 
1  & 0 & 24 & 18 & 9 & 23 \\ 
\hline 
0 & 1 & 11 & 7 & 17 & 11 \\ 
\hline 
0 & 0 & 1 & 24 & 0 & 17 \\ 
\hline 
\end{tabular} \\
table des inverses\\
\begin{tabular}{|c|c|}
\hline 
x  & x-1 \\ 
\hline 
1 & 1 \\ 
\hline 
3 & 9 \\ 
\hline 
5 & 21 \\ 
\hline 
7 & 15 \\ 
\hline 
9 & 3 \\ 
\hline 
11 & 19 \\ 
\hline 
15 & 7 \\ 
\hline 
17 & 23 \\ 
\hline 
19 & 11 \\ 
\hline 
21 & 5 \\ 
\hline 
23 & 17 \\ 
\hline 
25 & 25 \\ 
\hline 
\end{tabular} 

tableau des lettres \\
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline 
a & b & c & d & e & f & g & h & i & j & k & l & m & n & o & p & q & r & s & t & u & v & w & x & y & z \\ 
\hline 
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 \\ 
\hline 
\end{tabular}\\
on saute des étapes\\
Matrice Finale
$\begin{pmatrix}
1 & 0 & 0 \\ 
0 & 1 & 0 \\ 
0 & 0 & 1
\end{pmatrix} $
$\begin{pmatrix}
4 & 9 & 15 \\ 
15 & 17 & 6 \\ 
24 & 0 & 17
\end{pmatrix} $

$\begin{array}{cccccccccccc}
l & n & s & h & d & l & e & w & m & t & r & w \\ 
11 & 13 & 18 & 7 & 3 & 11 & 4 & 22 & 12 & 19 & 17 & 22 \\ 
15 & 0 & 24 & • & • & • & • & • & • & • & • & • \\ 
p & a & y & • & • & • & • & • & • & • & • & •
\end{array} $

une matrice est inversible si sont déterminant est premier avec la base du code (pour nous premier avec 26)

\section{Attaque d'un chiffrement d'un décalage}

\section{Chiffrement polyalphabetique}
\paragraph{Indice de coincidence}
texte de n lettres, on calcule le nombre de "A", nombre de B, ..., nombre de Z, et on fait $\frac{N_A (N_A -1) + N_B(N_B-1)+...+N_Z(N_Z-1)}{NombreLettres*NombreLettres-1}$
\paragraph{Attaque du chiffrement de Vigenère}
\begin{itemize}
\item Trouver la taille de la clé
\begin{itemize}
\item Sans l'indice de coincidence
\begin{itemize}
\item Recherche de chaines répétitives
\item Table des diviseurs pour la distance entre deux répétitions
\item Taille de la clé est probablement l'un des diviseurs de la majorité des distances
\end{itemize}
\item Avec l'indice de coincidence
\begin{itemize}
\item Calculer l'indice de coincidence en supposant la taille de la clé
\item Avec une taille de 1, on calcule l'indice sur la totalité du texte
\item Avec une taille de n, on établit n textes $T_1,T_2,...,T_n$ à partir de l'original T tels que, $T_i$ ets composé des lettres $T[I+k*n]$ avec i+k*n < Taille de T
\end{itemize}
\end{itemize}
\item Analyse statistique pour déterminer les lettres de la clé (faire pour chaque sous groupe une analyse de fréquence et récup lé plus fréquence et supposer que c'ets E, on toruve la lettre qui code chaque petit bout, on decode avec la clé et on recup le texte en clair).
\end{itemize}

\paragraph{Sûreté de chiffrement } la s\^ureté d'un chiffrement repose sur deux éléments 
\begin{itemize}
\item la force de  l'algorithme
\item la longueur de la clé
\end{itemize}
Même si le nombre de clé pour un chiffrement par substitution est phénoménal, l'algorithme est faible\\
La longueur de la clé permet de renforcer la sécurité car si l'algo est résistant, la force brute est la seule méthode sure pour déchiffrer , mais le nombre d'étape est géant pour décrypter si la clé est longue

\paragraph{Machine enigma}
première machine à chiffrer électriquement un message, composée de 
\begin{itemize}
\item tableau de fiche (définie les permutations alphabétique)
\item des rotors mélange certaines substitutions, le rotor crée une nouvelle substitution à chaque frappe d'un caractère, en tournant d'un cran, au bout de 26 caractères, le rotor se retrouve en position initiale, le second à un câblage différents du premier, et celui ci tourne d'un cran lorsque le premier a fait une révolution, donc en 26*26 caractère, on se retrouve en configuration initiale, puis un troisième rotor sur le même principe)
\item le réflecteur, situé à la sortie du troisième rotor. A un câblage qui fait que la lettre originale est liée électriquement à la lettre chiffrée
\end{itemize}

echec\\
\begin{itemize}
\item un traître donne deux documents aux alliés deux doc pour reconstruire une machine
\item il donne aussi un carnet de clés par moi spécifiant la clé du jour, une clé c'est la position des rotors, ainsi que la position initiale des rotors
\item Avant d'envoyer un message, mise en place d'une autre clé(position initiale des rotors) avec laquelle le message sera chiffré
\end{itemize}

\section{Chiffrement symétriques modernes : DES et AES}
\paragraph{} DES : Data Encryption Standard, était le plus utilisé, adopté en 1977, il servait par exemple pour 
\begin{itemize}
\item transactions bancaires
\item codes pin
\item SSL
\end{itemize}
Chiffrement symétrique à clé secrète : chiffre/déchiffre par l'intermédiaire de clé secrète, opère sur blocs de bits, plus les blocs sont grands, plus on cache la structure du texte, mais plus les blocs sont grands, plus les clefs sont gigantesques
\paragraph{Chiffrement de Feistel}
Effectuer plusieurs chiffrement simple pour simuler un chiffrement.\\
Feistel propose une structure générique pour le chiffrement par blocs
\paragraph{Exercice}
M message : 1,0,1,1,1,0\\
clé K : 0,0,1,1,1,0 \\
K1 = 0,1,1\\
K2 = 0,1,0\\
$f = \oplus$\\\\

L[0] = 1,0,1 R[0]=1,1,0\\
L[1] = 1,1,0 R[1] = R[0] $f$ K[1] $\oplus$ L[0] = 1,0,1 $\oplus$ 1,0,1 = 0,0,0\\
L[2] = 0,0,0 R[2] = R[1] $f$ K[2] $\oplus$ L[1] = 0,1,0 $\oplus$ 1,1,0 = 1,0,0\\
C = 0 0 0 1 0 0 \\\\

dechiffre\\
L[i] = R[i-1] , L[i-1] = L[i] $f$ K[i] $\oplus$ R[i]\\
L[2] = 0,0,0 R[2] = 1,0,0\\
R[1] = 0 0 0 L[1]= L[2] $f$ K[2] $\oplus$ R[2] = 0,1,0 $\oplus$ 1,0,0 = 1,1,0\\
R[0] = L[1] = 1,1,0 L[0] = L[1] $f$ K[1] $\oplus$ R[1] = 1,0,1 $\oplus$ 0,0,0 = 1,0,1\\
 
\subsection{DES} 
\paragraph{DES}
chiffrement par bloc de 64 bits, clé de 56 bits, input : M un bloc de 64 bits, et une clé de 56 bits,  le soucis ce'st que la clé fait réellement 48 bits, et les blocs gauche et droite font 32bits
\paragraph{passage de 32 à 48 bits}
le E-box fait un réarrangement des bits pour rajouter des bits 

\paragraph{passage de 48 a 32 bits}
il y a 8 S-box, on decoupe le message sortant en 8 morceaux de 6 bits puis on passe chaque nouveau bloc dans la s-box \\
$\begin{pmatrix}
d2..d5/d1d6 & 00 & 01 & 10 & 11 \\ 
0000 & 14 & 0 & 4 & 12 \\ 
... & ... & ... & ... & ...
\end{pmatrix} $
on retrouve avec quels 4bits on doit recoder le bloc, on retrouve donc 8 blocs de 4 bits soit 32 bits.

\paragraph{Déchiffrement} comme le schéma de feistel, il faut reprendre l'algorithme dans l'autre sens pour déchiffrer

\paragraph{Sûreté du DES}
pour le renforcer, les gens on fait un DES double avec deux clé\\
toutefois , il nous est possible de montrer que seulement avec $2^{57}$ clé au lieu de $2^{112}$
car avec un algorithme de rendez-vous, nous pouvons d'un coté tester un le déchiffrement de C avec toutes les clefs possibles, et un chiffrement de M avec toutes les clefs possible, et trouver une correspondance

\subsection{AES - Advanced Encryption Standard}
\paragraph{Corps de Galois} $F_{256}$ : l'ensemble des polynômes de degré 7 avec les coefficient égaux à 0 ou 1.\\
ensuite on représente en  binaire/décimale/hexadécimale des polynômes\\
$X^6+X^4+X^2+X+1 = 01010111 = 87_d =57_h$ 

\paragraph{Ex0 } dans le monde de Galois , combien font 87*163
87 = 01010111 = $X^6+x^4+X^2+X^1+1$\\
163 = 1010 0011 = $X^7 + X^5 + X^1+1$\\
= $X^{13}+X^{11}+x^9+x^8+x^7
+x^{11}+x^9+x^7+x^6+x^5
+x^7+x^5+x^3+x^2+x^1+x^6+x^4+x^2+x^1+1
= x^{13}+2x^{11}+2x^9+x^8+3x^7+2x^6+2x^5+x^4+x^3+2x^2+2x^1+1$\\
$=x^{13}+x^8+x^7+x^4+x^3+1 = 10 0001 1001 1001 = 8601$\\
l'addition de polynomes de degré 7 donne un degré 7
mais la multiplication donne des polynomes trop grand, on fais le modulo du resultat avec\\ $x^8+x^4+x^3+x+1$

\paragraph{}
chiffrement symétrique, blocs de 128 bits, clé de 128,192,256 bits.\\
on vois notre bloc comme 16 peits blocs de 8 bits, soit 16 polynomes de degré 7 dans une matrice 4*4 que l'on appelle état\\
pas de schéma de feistel\\
schéma de substitution/permutations sur l'état entier



\section{9 Octobre 2013}
\subsection{AES}
\paragraph{}
on prend le message, on vais un XOR avec la clé k0, ensuite on passe dans bytesub, puis dnas shiftrow, puis dnas mixColumn fin de premiere ronde, puis on XOR k1, puis bytesub, puis shiftrow, puis pas de mixcolumn car derniere ronde, puis XOR derniere clé (ici k2) et on obtient C\\

M=
$\begin{array}{cc}
1010 & 1000 \\ 
0100 & 0110
\end{array} $\\

K=
$\begin{array}{cc}
1111	 & 1010 \\ 
0100 & 1101
\end{array} $\\

K1=
$\begin{array}{cc}
0111 & 1101 \\ 
1001 & 0100
\end{array} $\\

K2=
$\begin{array}{cc}
0111 & 1010 \\ 
0011 & 0111 
\end{array} $\\

M$\oplus$K=
$\begin{array}{cc}
0101 & 0010 \\ 
0000 & 1011
\end{array} $\\

byteSub(M$\oplus$K)=
$\begin{array}{cc}
1111 & 1101 \\ 
1110 & 1100
\end{array} $\\

shiftRow(bytesub(M$\oplus$K)=
$\begin{array}{cc}
1111 & 1101 \\ 
1100 & 1110
\end{array} $\\

tour1 : MixColumn *shiftRow(bytesub(M$\oplus$K))=
$\begin{array}{cc}
1001 & 1011 \\ 
1010 & 1000
\end{array} $\\
fin du tout\\

\subsection{Chiffrement à clé publique}
\paragraph{} la clé publique est connue pour chiffrer  un message , qui sera decryptable par le destinataire avec sa clé privée

\end{document}